package sort;

/**
 * 堆排序
 * https://www.jianshu.com/p/11655047ab58
 * Created by JiaJia on 2019/8/15 0015.
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] nums={5,1,6,3,11,7,9,2,13};
        heapSort(nums);
        for (int i = 0; i <nums.length ; i++) {
            System.out.println(nums[i]);
        }
    }

    private static void heapAdjust(int[] nums,int len,int i){
        //i表示把第I个元素下沉到正确的位置，也就是往下找比它大的子节点并交换
        //len表示前面len个节点
        int k=i,temp=nums[i],index=2*k+1;
        while (index<len){
            if (index+1<len){
                if (nums[index]<nums[index+1]){
                    index=index+1;
                }
            }
            if (nums[index]>temp){
                nums[k]=nums[index];
                k=index;
                index=2*k+1;
            }else {
                break;
            }
        }
        nums[k]=temp;


    }
    private static void heapSort(int[] nums){
        //构建初始堆，从第一个非叶子节点往前开始调整，左右孩子节点大的交换到父节点
        for (int i = (nums.length)/2-1; i >=0 ; i--) {
            heapAdjust(nums,nums.length,i);
        }
        //排序，把最大的节点放在堆尾，
        for (int i = nums.length-1; i >=1 ; i--) {
            int tmp=nums[0];
            nums[0]=nums[i];
            nums[i]=tmp;
            heapAdjust(nums,i,0);
        }
    }




}